题目传送门:http://oi.cdshishi.net:8080/Problem/1020
这货,本来以为是裸的主席树
结果被卡空间
最后还是只有写优化的主席树
另外,值域会爆int
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int M = 19000000; const int N = 260000+9; int n,m,POS[N],T; LL vout,arr[N],NV[N],hash[N]; inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } namespace Chair_Tree{ #define CT Chair_Tree #define lowbit(x) ((x)&-(x)) int ch[M][2],sz[M],root[N*2],cnt,ans_tmp; void modify(int p, int &w, int v, int l, int r, int delta) { w = ++cnt; sz[w] = sz[p] + delta; memcpy(ch[w],ch[p],sizeof(ch[w])); if (l < r) { int mid = l + r + 1 >> 1; if (v < mid) modify(ch[p][0],ch[w][0],v,l,mid-1,delta); else modify(ch[p][1],ch[w][1],v,mid,r,delta); } } inline void modify(int pos, int val, int delta){ for (int i=pos;i<=n;i+=lowbit(i)) modify(root[i],root[i],val,1,T,delta); } inline void build(){ for (int i=1;i<=n;i++) modify(root[i-1+n+1],root[i+n+1],arr[i],1,T,1); } void query(int w, int l, int r, int L, int R) { if (!w) return; else if (l <= L && R <= r) ans_tmp += sz[w]; else { int mid = L + R + 1 >> 1; if (l < mid) query(ch[w][0],l,r,L,mid-1); if (mid <= r) query(ch[w][1],l,r,mid,R); } } inline int query(int w, int l, int r) { ans_tmp = 0; query(w,l,r,1,T); return ans_tmp; } inline int query(int l ,int r, int L, int R){ if (l > r || L > R) return 0; int ret = 0; for (int i=r;i;i-=lowbit(i)) ret += query(root[i],L,R); for (int i=l-1;i;i-=lowbit(i)) ret -= query(root[i],L,R); ret += query(root[n+r+1],L,R); ret -= query(root[n+l-1+1],L,R); return ret; } }; int main(){ n = read(); for (int i=1;i<=n;i++) arr[i] = hash[++T] = read(); m = read(); for (int i=1;i<=m;i++) POS[i] = read(), NV[i] = hash[++T] = read(); sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1; for (int i=1;i<=n;i++) arr[i] = lower_bound(hash+1,hash+T+1,arr[i]) - hash; for (int i=1;i<=m;i++) NV[i] = lower_bound(hash+1,hash+T+1,NV[i]) - hash; CT::build(); for (int i=1;i<=n;i++) vout += CT::query(1,i-1,arr[i]+1,T); for (int i=1,pos,nv;m;m--,i++) { pos = POS[i]; nv = NV[i]; vout -= CT::query(1,pos-1,arr[pos]+1,T); vout -= CT::query(pos+1,n,1,arr[pos]-1); vout += CT::query(1,pos-1,nv+1,T); vout += CT::query(pos+1,n,1,nv-1); CT::modify(pos, arr[pos], -1); CT::modify(pos, nv, 1); arr[pos] = nv; cout<<vout<<endl; } return 0; }
Your style is so unique compared to many other people. Thank you for publishing when you have the opportunity,Guess I will just make this bookmarked.2
Heya this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding skills so I wanted to get advice from someone with experience. Any help would be greatly appreciated!